package com.fan.hanshunping.algorithm.dp;

/**
 * @author :  PF_23
 * @Description : DP-背包问题
 * @date : 2020/04/16.
 */

public class KnapsackProblem {

    public static void main(String[] args) {
        //物品的重量
        int[] w = {1, 4, 3};
        //物品的价值 这里 val[i] 就是前面讲的 v[i]
        int[] val = {1500, 3000, 2000};
        //背包的容量
        int m = 4;
//        String zeroOnePack = zeroOnePack(m, w.length, w, val);
//        System.out.println(zeroOnePack);
        int i = ZeroOnePack2(m, w.length, w, val);
        System.out.println(i);
    }
    public static String zeroOnePack(int V, int N, int[] weight, int[] value) {
        //初始化动态规划数组
        int[][] dp = new int[N + 1][V + 1];

        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < V + 1; j++) {
                //如果第i件物品的重量大于背包容量j,则不装入背包
                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }


        //则容量为V的背包能够装入物品的最大值为
        int maxValue = dp[N][V];
        System.out.println("背包能装入的最大价值为：" + maxValue);
        //逆推找出装入背包的所有商品的编号
        int j = V;
        String numStr = "";
        for (int i = N; i > 0; i--) {
            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
            if (dp[i][j] > dp[i - 1][j]) {
                numStr = i + " " + numStr;
                j -= weight[i - 1];
            }
            if (j == 0) {
                break;
            }
        }
        return numStr;
    }

    /**
     * 优化： 思路：
     * 只用一个一维数组记录状态，dp[i]表示容量为i的背包所能装入物品的最大价值
     * 用逆序来实现
     *
     * @param V
     * @param N
     * @param weight
     * @param value
     * @return
     */
    public static int ZeroOnePack2(int V, int N, int[] weight, int[] value) {
        //动态规划
        int[] dp = new int[V + 1];
        for (int i = 1; i < N + 1; i++) {
            //逆序实现
            for (int j = V; j >= weight[i - 1]; j--) {
                dp[j] = Math.max(dp[j - weight[i - 1]] + value[i - 1], dp[j]);
            }
        }
        return dp[V];
    }
}

